home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 501-525 / disk_519 / avlsort / avltree.man < prev    next >
Text File  |  1992-05-06  |  8KB  |  199 lines
  1.  
  2.  
  3.  
  4.      AVL(n)                      UNIX 5.0                       AVL(n)
  5.  
  6.  
  7.  
  8.      NAME
  9.           avl - General Purpose AVL tree subroutines
  10.  
  11.      SYNOPSIS
  12.           #include "avl.h"
  13.  
  14.           AVLNODE *avlfind( treeP, keyP )
  15.                AVLTREE *treeP;
  16.                void *keyP;
  17.  
  18.           int avlinsert( treeP, keyP, dataP )
  19.                AVLTREE *treeP;
  20.                void  *keyP;
  21.                void *dataP;
  22.  
  23.           int avldelete( treeP, keyP )
  24.                AVLTREE *treeP;
  25.                void *keyP;
  26.  
  27.      SYNOPSIS
  28.           avlfind searches an AVL tree for a node that matches a given
  29.           key, according to the key comparison routine specified in
  30.           the tree description structure.  treeP is the address of the
  31.           tree description block; keyP is the address of a key; this
  32.           is given to the key comparison routine specified in the tree
  33.           description structure.  Its interpretation, if any, is left
  34.           to the comparison routine.  avlfind returns the address of
  35.           the node found, or NULL if none found.
  36.  
  37.           avlinsert inserts a new node into an AVL tree.  treeP is the
  38.           address of the tree description structure; keyP is the
  39.           address of a key; this address is given to the key
  40.           comparison routine and the node construction routines
  41.           specified in the tree description structure, and is not
  42.           otherwise handled by avlinsert. avlinsert returns -1 if
  43.           there was a failure of some sort; 0 if the node was
  44.           inserted; 1 if the key was already in the tree (and the node
  45.           construction routine rejected the duplication).
  46.  
  47.           avldelete deletes a node from an AVL tree.  treeP is the
  48.           address of the tree description structure; keyP is the
  49.           address of the key that identifies the node to be deleted -
  50.           it is given to the key comparison routine specified in the
  51.           tree description structure in the process of locating the
  52.           node to delete.  avldelete returns 0 if the node was
  53.           deleted, -1 if it was not found in the tree.
  54.  
  55.           Note well: all node addresses refer to the address of
  56.           AVLNODE structures; typically an AVLNODE structure will be
  57.           imbedded in an enveloping structure that contains key and/or
  58.           data information.  Nevertheless, the AVL routines require,
  59.           pass, and return the AVLNODE node structure address, not the
  60.  
  61.  
  62.  
  63.      Page 1                                           (printed 6/3/88)
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70.      AVL(n)                      UNIX 5.0                       AVL(n)
  71.  
  72.  
  73.  
  74.           address of the containing structure (if any).  In most
  75.           cases, arranging to have the AVLNODE structure address be
  76.           the same as the general structure address (i.e., be the
  77.           first element within that structure) is the best thing to
  78.           do, so that address translation is not necessary.  In the
  79.           case of multiple membership, this is obviously not possible.
  80.  
  81.      DESCRIPTION
  82.           These routines are a general-purpose implementation of AVL
  83.           trees in C.  They are derived, with small changes, from the
  84.           description of AVL (Adelson-Velskii and Landis) trees found
  85.           in Knuth's "The Art of Computer Programming Volume 3:
  86.           Searching and Sorting" (Addison-Wesley, 1973) pgs 451-471.
  87.  
  88.           These routines deal with tree maintenance only.  They are
  89.           only concerned with the arrangement of the nodes in the
  90.           tree.  Composition of those nodes is left to outside
  91.           knowledge.  The caller must construct an AVL tree header
  92.           structure which specifies routines that deal with nodes
  93.           (comparison, construction, and deletion).  AVL nodes
  94.           therefore do not need to contain any specific kind of key,
  95.           or data, or even both key and data.  For instance, the
  96.           address of an AVL node may imply this information without
  97.           the information being present.  Also, multiple AVL nodes may
  98.           be attached to a particular piece of data so that that data
  99.           may be keyed and accessed in multiple ways.
  100.  
  101.      RELATED INFORMATION
  102.           The AVL tree header (AVLTREE) has the following structure:
  103.  
  104.           typedef struct {
  105.               /* Tree parameters */
  106.               AVLNODE    *t_rootP;      /* Ptr to root node */
  107.  
  108.               /* Handler functions for the tree */
  109.               int        (*t_cmprtc)();      /* Compare two keys */
  110.               AVLNODE    *(*t_mknode)();          /* Node maker */
  111.               int        (*t_rmnode)();      /* Node destroyer */
  112.             } AVLTREE;
  113.  
  114.  
  115.           Before any use of AVL routines, the handler functions must
  116.           be specified.  We'll refer to them as simply cmprtc, mknode,
  117.           and rmnode.
  118.  
  119.           int cmprtc( keyP, nodeP )
  120.                void *keyP;
  121.                AVLNODE   *nodeP;
  122.  
  123.           AVLNODE *mknode( treeP, keyP, dataP, enodeP )
  124.                AVLTREE   *treeP;
  125.                void *keyP;
  126.  
  127.  
  128.  
  129.      Page 2                                           (printed 6/3/88)
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136.      AVL(n)                      UNIX 5.0                       AVL(n)
  137.  
  138.  
  139.  
  140.                void *dataP;
  141.                AVLNODE   *enodeP;
  142.  
  143.           void rmnode( treeP, nodeP )
  144.                AVLTREE *treeP;
  145.                AVLNODE   *nodeP;
  146.  
  147.  
  148.           cmprtc compares a given key against a key associated with a
  149.           node.  keyP is the address of a key (interpreted in whatever
  150.           way is applicable); nodeP is the address of an AVLNODE
  151.           structure to which the key should be compared.  It shall
  152.           return -1 if keyP is less than the key associated with nodeP
  153.           key; 0 if they match; +1 if keyP is greater than the key
  154.           associated with nodeP.
  155.  
  156.           mknode creates a node on behalf of tree insertion.  treeP is
  157.           the address of the tree description structure; keyP is the
  158.           address of any key associated with the node; dataP is the
  159.           address of any data associated with the node; enodeP is the
  160.           address of any node that already exists in the tree for
  161.           keyP. If enodeP is not NULL, then this routine is being
  162.           called to replace the data in an existing node.  It can
  163.           signal its unwillingness to do this by returning NULL as its
  164.           return value, otherwise it must return the address of the
  165.           existing node.  Otherwise (if enodeP is not NULL), this
  166.           routine should allocate (or otherwise create) a new node and
  167.           fill it in.  mknode shall return the address of the node
  168.           constructed, or NULL if no node was made.
  169.  
  170.           rmnode is called to delete a node and its information.
  171.           treeP is the address of the tree description structure;
  172.           nodeP is the address of the node to delete.  It is called
  173.           when a node is removed from a tree; it may do what it likes
  174.           and does not return any information.
  175.  
  176.      FILES
  177.           avl.h avl.c avl.n avltest.c
  178.  
  179.      RESTRICTIONS
  180.           This software may be used at will, provided that all credits
  181.           and style be left in place, and that its distribution is not
  182.           restricted.  Bug fixes and improvements are welcomed, please
  183.           send these back to me at mem@zinn.MV.COM
  184.  
  185.      CREDITS TO
  186.           Mark E. Mallett  (mem@zinn.MV.COM)
  187.  
  188.      BUGS
  189.           You tell me..
  190.  
  191.  
  192.  
  193.  
  194.  
  195.      Page 3                                           (printed 6/3/88)
  196.  
  197.  
  198.  
  199.